package com.skh.hash;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * created by skh on 2019/6/18
 * 四数之和
 */
public class FourSum {

	/*
	给定一个包含n个整数的数组S, S中是否有元素a、b、c和d使得a + b + c + d = target?找出数组中所有唯一的四胞胎，给出目标的和。
	注意:
	四连音(a、b、c、d)中的元素必须按非降序排列。(即a≤b≤c≤d)
	解集不能包含重复的四联体。

	For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)
	 */

	public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {

		//通过set来去重
		Set<ArrayList<Integer>> result = new HashSet<>();

		int length = num.length;
		int sum, left, right;
		Arrays.sort(num);
		for (int i = 0; i < length-3; i++) {
			for (int j = i + 1; j < length-2; j++) {
				left = j + 1;
				right = length - 1;
				while (left < right) {
					sum = num[i] + num[j] + num[left] + num[right];
					if (sum == 0) {
						ArrayList<Integer> temp = new ArrayList<>();
						temp.add(num[i]);
						temp.add(num[j]);
						temp.add(num[left]);
						temp.add(num[right]);
						result.add(temp);
						left++;
						right--;
					} else if (sum < 0) {
						left++;
					} else {
						right--;
					}
				}
			}
		}

		return new ArrayList<>(result);
	}

	public static void main(String[] args) {
		FourSum fourSum = new FourSum();
		int[] i = {1, 0, -1, 0, -2, 2};
		ArrayList<ArrayList<Integer>> arrayLists = fourSum.fourSum(i, 0);
		System.out.println("arrayLists = " + arrayLists);
	}

}
